#include "NDOLinkedList.h"
#include <iostream>
using namespace std;

NDOLinkedList::NDOLinkedList(int a[],int n)
{
	if (n<=0)
	{
		this->head = new LinkedNode();
		this->length = 0;
		return;
	}
	int temp;
	LinkedNode* p, * pre;
	p = new LinkedNode(a[0]);
	this->head = new LinkedNode(0, p);
	pre = this->head;
	for (int i = 1; i < n; i++)
	{
		pre = this->head;
		temp = a[i];
		while (pre->next!=nullptr && temp>pre->next->data)
		{
			pre = pre->next;
		}
		p = new LinkedNode(a[i], pre->next);
		pre->next = p;
	}
	this->length = n;
}

NDOLinkedList::NDOLinkedList()
{
	this->length = 0;
	this->head = new LinkedNode();
}

NDOLinkedList::~NDOLinkedList()
{
	LinkedNode* p, * pre;
	p = this->head;
	pre = p->next;
	while (pre!=nullptr)
	{
		delete p;
		p = pre;
		pre = pre->next;
	}
	delete p;
}

NDOLinkedList* NDOLinkedList::merge(NDOLinkedList* list)
{
	NDOLinkedList* newList = new NDOLinkedList();
	newList->length = this->length + list->length;
	LinkedNode* f = this->head->next;
	LinkedNode* s = list->head->next;
	LinkedNode* p = newList->head;
	LinkedNode* pre;
	while (f != nullptr && s != nullptr)
	{
		if (f->data < s->data)
		{
			pre = new LinkedNode(f->data);
			p->next = pre;
			p = p->next;
			f = f->next;
		}
		else
		{
			pre = new LinkedNode(s->data);
			p->next = pre;
			p = p->next;
			s = s->next;
		}
	}
	while (f != nullptr)
	{
		pre = new LinkedNode(f->data);
		p->next = pre;
		p = p->next;
		f = f->next;
	}
	while (s != nullptr)
	{
		pre = new LinkedNode(s->data);
		p->next = pre;
		p = p->next;
		s = s->next;
	}
	return newList;
}

void NDOLinkedList::displayList()
{
	LinkedNode* p = this->head->next;
	while (p!=nullptr)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

LinkedNode::LinkedNode()
{
	this->next = nullptr;
	this->data = 0;
}

LinkedNode::LinkedNode(int a)
{
	this->next = nullptr;
	this->data = a;
}


LinkedNode::LinkedNode(int a, LinkedNode* n)
{
	this->data = a;
	this->next = n;
}

LinkedNode::~LinkedNode()
{
}

int* initialRandomArray(int n)
{
	int a;
	int* array = new int[n];
	for (int i = 0; i < n; i++)
	{
		a = rand() % 100;
		array[i] = a;
	}
	return array;
}

void displayArray(int* array,int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << array[i] << " ";
	}
	cout << endl;
}
